package pri.zjy.string;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhangjy
 * @description 赎金信
 * @date 2025/4/1 16:59
 */
public class CanConstruct_383 {

    public static void main(String[] args) {
        CanConstruct_383 canConstruct383 = new CanConstruct_383();
//        String ransomNote = "a", magazine = "b";
//        String ransomNote = "aa", magazine = "ab";
        String ransomNote = "aa", magazine = "aab";
        System.out.println(canConstruct383.canConstruct(ransomNote, magazine));
    }

    /**
     * 个解-哈希表统计次数；
     * T(n) = O(m + n)，其中 m 是字符串 ransomNote 的长度，n 是字符串 magazine 的长度，我们只需要遍历两个字符一次即可。
     * S(n) = O(m)，其中 m 是字符串 ransomNote 的长度。
     */
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<String, Integer> noteMap = new HashMap<>();
        // 记录ransomNote字符出现个数
        for (int i = 0; i < ransomNote.length(); i++) {
            String key = String.valueOf(ransomNote.charAt(i));
            if (noteMap.containsKey(key)) {
                noteMap.put(key, noteMap.get(key) + 1);
            } else {
                noteMap.put(key, 1);
            }
        }
        // 判断能否有magazine组成
        for (int i = 0; i < magazine.length(); i++) {
            String key = String.valueOf(magazine.charAt(i));
            if (noteMap.containsKey(key)) {
                int count = noteMap.get(key);
                if (count > 1) {
                    noteMap.put(key, count - 1);
                } else {
                    noteMap.remove(key);
                }
            }
        }

        return noteMap.isEmpty();
    }

}
